% small.tex
\documentclass{beamer}
\usetheme{Rochester} 
\usepackage[serbianc]{babel}
\newtheorem{inv}{Инваријанта графа} 
\newtheorem{ged1graph}{GED=1 граф}
\newtheorem{ged1set}{GED=1 скуп}  
\newtheorem{strsen}{Структурна осетљивост} 
\newtheorem{abbr}{Максимални отклон}  
\usepackage[noline]{algorithm2e}

\title{МАСТЕР РАД}
\subtitle{Примена рачунарстава високих перфроманси у графосвкихм прорачунима}
\author[М. Вучић]{Милош Вучић}
\institute[ИМИ]{
  Институт за математику и информатику\\
  Природно-математички факултет\\
  Универзитет у Крагујевацу\\[1ex]
}
\date[Октобар 2013]{14. октобар 2013}

\begin{document}


%--- the titlepage frame -------------------------%
\begin{frame}[plain]
  \titlepage
\end{frame}


%--- the presentation begins here ----------------%
\begin{frame}{Графови у хемији}
  
  \textbf{Плерограм} се конструише тако што се сваки атом приказује чвором, а два чвора су суседна ако су одговарајући атоми хемијски повезани.
 
  \begin{figure}[htb]
	\begin{center}
	\leavevmode
	\includegraphics[width=100mm]{images/plerogram.png}
	\end{center}
	\end{figure}
\end{frame}


\begin{frame}{Графови у хемији}
\textbf{Кенограм} се конструише тако што се чворовима приказују сви атоми осим водоникових. На тај начин кенограм репрезентује само угљенични скелет органског молекула
  \begin{figure}[htb]
	\begin{center}
	\leavevmode
	\includegraphics[width=100mm]{images/kenogram.png}
	\end{center}
	\end{figure}
\end{frame}



\begin{frame}{Молекулски структурни дескриптори}
\begin{itemize}
\item Молекулска структура је ненумерички појам
\item Једној одређеној супстанци се могу придружити разни молекулски подаци, који одговарају њеним физичко-хемијским особинама


\end{itemize}
\end{frame}

\begin{frame}{Молекулски структурни дескриптори}
\begin{inv}
Нека је $I=I(G)$ математички ентитет (број, матрица, полином, вектор, група,...) које се на неки начин придружује графу $G$. Ако је задовољен услов да за свака два изоморфна графа $G_1$ и $G_2$ важи $I(G_1)=I(G_2)$ онда се каже да је $I$ \textbf{инваријанта графа} или да је $I$ графовска инваријанта.
\end{inv}
\begin{itemize}
\item Број чворова, брoј грана, цикломатични број, број савршених спаривања, полином спаривања, карактеристични полином, спектар графа.
\item Инваријанте се могу довести у везу са физичко-хемијским особинама молекула
\end{itemize}
\end{frame}


\begin{frame}{Молекулски структурни дескриптори}
\begin{itemize}
\item Молекулски структурни дескриптори засновани на молекулском графу често се називају \textbf{тополошки индекси}
\item Физичко-хемијске особине једињења су условљене структуром молекула од којих се то једињење састоји
\item Повезано нпр. са тачкама кључања алкана, топлотом изомеризације и топлотом испаравања, напоном паре, површинским напоном, индексом преламања, међумолекулским силама, предвиђањем густине, моларном запремином, брзином простирања звука
\end{itemize}
\end{frame}




\begin{frame}{Молекулски структурни дескриптори}
Валидан дескриптор има следеће карактеристике:
\begin{itemize}
\item Могућност непосредне структурне интерпретације.
\item Корелација са макар једном физичко-хемијском особином.
\item Могућност разликовања изомера.
\item Линеарна независност.
\item Једноставност.
\item Да није заснован на физичко-хемијским особинама.
\item Да није, на тривијлан начин, повезан са другим структурним дескрипторима.
\item Да се може ефикасно израчунати.
\item Да је дефинисан на основу лако разумљивих структурних концепата.
\item Да има коректну зависност од величине молекула.
\item Да се постепено мења при малим променама у молекулској структури - Глаткост
\end{itemize}
\end{frame}






\begin{frame}{Квантификација глаткости тополошког индекса}
\begin{ged1graph}
Нека је $G$ неки граф. Нека су $v_r, v_s$ и $v_t$ неки чворови графа $G$, такви да $(v_r, v_s)\in E(G)$ и $(v_r, v_t) \not\in E(G)$. Са $G'$ обележавамо граф који се добије уклањањем $(v_r, v_s)$ из $E(G)$ и додавањем $(v_r, v_t)$ у $E(G)$. За граф $G'$ кажемо да је настао минималном променом у графу $G$ (једна грана је замењена новом). 
\end{ged1graph}
\end{frame}


\begin{frame}{Квантификација глаткости тополошког индекса}
\begin{ged1set}
Нека је $S(G)$ скуп графова. Скуп $S(G)$ правимо тако што прво претходном трансфромацијом $G \rightarrow G'$ генеришемо све могуће графове $G'$. Да би генерисани граф $G'$ додали у $S(G)$, он мора да задовољава следеће услове:
\begin{itemize}
\item $G'$ је повезан граф,
\item $G'$ није изоморфан са $G$,
\item $G'$ није изоморфан ни са једним елементом из $S(G)$.
\end{itemize}
\end{ged1set}
\end{frame}

\begin{frame}{Квантификација глаткости тополошког индекса}
\begin{strsen}
\textbf{Структурна осетљивост} индекса $TI$ у односу на граф $G$ је вредност:
\begin{equation}
\nonumber
SS(G) = \sigma(TI) = \sqrt{ \frac{1}{|S(G)|} \sum_{G' \in S(G)} (TI(G') - \mu(TI))^2 }
\end{equation}
\end{strsen}
\end{frame}

\begin{frame}{Квантификација глаткости тополошког индекса}
\begin{abbr}
\textbf{Максимални отклон} тополошког индекса $TI$ у односу на граф $G$ је вредност:
\begin{equation}
\nonumber
 Abr(TI, G) = \max_{G' \in S(G)} \bigg\vert TI(G') - TI(G)\bigg\vert .
\end{equation}
\end{abbr}
\end{frame}

\begin{frame}{Квантификација глаткости тополошког индекса}
Област истраживања:
\begin{itemize}
\item Индекси засновани на степену чвора
\begin{equation}
TI(G) = \sum_{(u,v) \in E(G)} F(d_u, d_v)
\nonumber
\end{equation}
\item Логично је упоређивати разноразне вредности $TI$ за графове који имају исти број чворова и грана
\end{itemize}
\end{frame}


\begin{frame}{Квантификација глаткости тополошког индекса}
\begin{center}
\fontsize{9}{9}\selectfont
\begin{tabular}{l r}
Број чворова & Број неизоморфних стабала\\
\hline
&\\
1& 1 \\
2& 1\\
3 &1\\
4 &2\\
5 &3\\
6 &6\\
7 &11\\
8 &23\\
9 &47\\
10 &106\\
11 &235\\
12 &551\\
13 &1,301\\
14 &3,159\\
15 &7,741\\
16 &19,320\\
17 &48,629\\
18 &123,867\\
19 &317,955\\
20 &823,065\\
\end{tabular}
\end{center}
\end{frame}

\begin{frame}{Квантификација глаткости тополошког индекса}
\centering
 \begin{tabular}{l r}
Име индекса & Матеметичка дефиниција\\
\hline
\textit{Randić}‎ & $R=\sum_{u,v \in E(G)} \frac{1}{\sqrt{d_u d_v}}$ \\
\textit{First Zagreb} & $M1=\sum_{u,v \in E(G)} (d_u + d_v)$ \\
\textit{Second Zagreb} & $M2=\sum_{u,v \in E(G)}(d_u d_v)$ \\
\textit{Atom-bond connectivity} & $ABC=\sum_{u,v \in E(G)} \sqrt{\frac{d_u + d_v -2}{d_u d_v}}$ \\
\textit{Sum-connectivity} & $SCI=\sum_{u,v \in E(G)}\frac{1}{\sqrt{d_u + d_v}}$ \\
\textit{First geometric-arithmetic} & $GA1=\sum_{u,v \in E(G)}\frac{2\sqrt{d_u d_v}}{d_u + d_v}$ \\
\textit{Augmented Zagreb} & $AZI=\sum_{u,v \in E(G)} \bigg ( \frac{d_ud_v}{d_u + d_v - 2} \bigg)^3$ \\
\textit{Harmonic} & $HI=\sum_{u,v \in E(G)}\frac{2}{d_u + d_v}$ \\
\label{table:indices}
\end{tabular}
\end{frame}



\begin{frame}{Квантификација глаткости тополошког индекса}
\fontsize{6}{6}\selectfont
\begin{algorithm}[H]
 \KwData{$T(n), EI, F$}
 \For{$T\in T(n)$}{
 $S(T)=\emptyset$\;
  \For{$node \in V(T)$}{
  	\For{$ neighbor \in \{neighbor: (node, neigbor) \in E(T)\}$}{
  		\For{$nonneighbor \in \{noneighbor: (node, nonneigbor) \not\in E(T)\}$}{
  			$T' \leftarrow T$\;
  			 $ E(T') \leftarrow E(T) - (node, neigbor) + (node, noneighbor)$\;
  			\If{($T'$ is connected) \textbf{and} ($T' \not\cong T$) \textbf{and} $(\neg\exists T_s \in S(T) : T'\cong T_s)$ }{
				$S(T) \leftarrow S(T) + T'$  			
  			}
  		}
  	}
  }

  \For{$index$ in $EI$}{
    	 $TI_T = \sum_{(d_u, d_v) \in E(T)} F[index](d_u, d_v)$ \;
  	 \vspace{1mm}
  	 $TIvalues = \{\sum_{(d_u, d_v) \in E(S)} F[index](d_u, d_v): S \in S(T)\}$\;
  	 \vspace{1mm}
  	 $SS[index] [T] = \sigma (TIvalues)$\;
  	 $Abr[index] [T] = \max_{\; TI_v \;\in \; TIvalues} \bigg\vert TI_v - TI_T\bigg\vert$\;
  }
  
 }
 

 \For{$index$ in $EI$}{
  	 $AverageSS = \frac{\sum_{T\in T(n)} SS[index][T] }{|T(n)|} $\;
  	 $AverageAbr = \frac{\sum_{T\in T(n)} Abr[index][T] }{|T(n)|} $\;
  	 \vspace{1mm}
  	 \textbf{print} \textit{index, AveragaeSS, AverageAbr}
  } 



 
 
\end{algorithm}
\end{frame}


\begin{frame}{Квантификација глаткости тополошког индекса}
Комплексност алгоритма:
\begin{itemize}
\item Број операција 
\begin{equation}
|T_n|\cdot (n \cdot C_1n \cdot C_2n \cdot (C_3n + C_4C_5n ) +C_6n)+ C_7n  = C_0n^4 + C_8n,
\label{eq:numop}
\nonumber
\end{equation}
\item  $O(n^4)$
\end{itemize}


\end{frame}


\begin{frame}{Аpache Hadoop}
\textit{HDFS}
\begin{itemize}
\item Величина блока 64 Mb
\item Репликација података
\item \textit{Java API, CLI}
\item \textit{Datanode, Namenode, Secondary Namenode}
\end{itemize}
\end{frame}



\begin{frame}{Аpache Hadoop}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=80mm]{images/HDFS.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Аpache Hadoop}
\textit{МapReduce}
\begin{itemize}
\item Ради са паровима кључ/вредност
\item Посао се састоји из више задатака
\item \textit{Tasktracker, Jobtracker}
\end{itemize}
\vspace{10mm}
\centering
\begin{tabular}{l c c}
& Улаз & Излаз\\
\hline
Фаза мапирања &\textit{ <k1,v1>}& \textit{list(<k2, v2>) }\\
Фаза редуковања &\textit{<k2, list(v2)>} &\textit{list(<k3, v3>) }\\
\end{tabular}
\end{frame}



\begin{frame}{Аpache Hadoop}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=80mm]{images/mrstruct.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Аpache Hadoop}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=65mm]{images/mrflow.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Софтвер за израчунавање глаткости}
Коришћени алати:
\begin{itemize}
\item \textit{Python, R}
\item \textit{Networkx}
\item \textit{Nauty}
\end{itemize}
\end{frame}


\begin{frame}{Софтвер за израчунавање глаткости}
\fontsize{11}{11}\selectfont
\textit{Graph6} формат
\begin{enumerate}
\item Горњи троугао матрице суседства се запише као бит вектор дужине $n(n-1)/2$, тако што се редом додају вредности матрице:
 $[0,0]$, $[0,1]$, $[0,2]$,..., $[0,n]$, $[1,1]$, $[1,2]$, $[1,n]$,..., $[n-1,n]$. Претпоставимо да је тај бит вектор записан у облику 100010110001110.
\item Додајемо нуле на крај, тако да укупан број битова буде дељив са шест. У нашем примеру додајемо три нуле и сада имамо бит вектор 100010110001110000. 
\item Бит вектор делимо у групе по 6 битова. Добијамо 100010 110001 110000.
\item Сваки скуп битова претварамо у декадни систем и додајемо вредност 63. Добијамо 97 112 111. 
\item Испред ових вредности додајемо вредност која одговара броју чворова графа увећану за 63. Добијамо 69 97 112 111.
\item Сваки од ових бројева представимо одговарајућим карактером из \textit{ASCII} кода. Добијамо вредност \textit{Еаpo}. 
\end{enumerate}
\end{frame}


\begin{frame}{Софтвер за израчунавање глаткости}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[height=75mm]{images/MyMR.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Софтвер за израчунавање глаткости}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[height=75mm]{images/ClassDiag.png}
\end{center}
\end{figure}
\end{frame}



\begin{frame}{Софтвер за израчунавање глаткости}
Провера изоморфности:
\begin{itemize}
\item \textit{is\_isomorhic}, \textit{VF2} алгоритам за проверу изоморфизма, комплексност варира између $O(n^2)$ - $O(n!n)$ 
\item Потребан је линеаран алгоритам
\item Тополошко обележавање коренског стабла + Хеш мапе 
\end{itemize}
\end{frame}





\begin{frame}{Софтвер за израчунавање глаткости}
\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}[H]
\Fn(\tcc*[h]{recursive function}){Label(node)}{
\textit{subtreeLabel} ← []\;
\textit{number←Length(node.children)}\;
\If{number == 0}{
	\textbf{return} 0
}
\textit{children} ← \textit{node.children}\;
\For{ child in children }{
\textit{subtreeLabels.add(Label(child))}
}
\textit{Sort(subtreeLables)}\;

\textbf{return} (\textit{number + ',' + subtreeLabels.joinWith(',')})\;
}
\end{algorithm}
\end{frame}



\begin{frame}{Софтвер за израчунавање глаткости}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=80mm]{images/label.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Софтвер за израчунавање глаткости}
Тополошко обележје некоренског стабла
\begin{itemize}
\item Јединствен чвор са максималним степенoм
\item Нека je $K(u)$ скуп повезаних компоненти графа који настаје када се из стабла уколни неки чвор $u$. Нека је $S$ скуп чворова такав да важи:
\begin{equation}
S = \{u \in V :\;  (\forall K \in K(u): |K| \leq \frac{|V|}{2}) \}
\nonumber
\end{equation}
\item Јединствени елемент из $S$
\item Лексикографски мање од два тополошка обележја коренских стабала са коренима у елементима скупа $S$.
\end{itemize}
\end{frame}


\begin{frame}{Софтвер за израчунавање глаткости}
\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}[H]
\Fn(\tcc*[h]{recursive function}){Shift(u)}{
\If{$\neg\exists v: (u,v) \in E \wedge w(v)> \frac{n}{2}$ }{
\Return \{u\}\;
}
\ElseIf{$\exists v: (u,v) \in E \wedge w(v) = \frac{n}{2}$}{
\Return \{u,v\}\;
}
\Else{
$v \leftarrow w: (w,u) \in E \wedge w(w) > \frac{n}{2} $\;
$w(u) = w(u) - w(v)$\;
$w(v)= w(u)+w(v)$\;
\Return \textit{Shift(v)}\;
}
}
\end{algorithm}
\end{frame}



\begin{frame}{Софтвер за израчунавање глаткости}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=80mm]{images/shift.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Скалабилност}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/scall.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Резултати за стабла са 6 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res6.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Резултати за стабла са 10 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res10.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Резултати за стабла са 15 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res15.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Резултати за стабла са 18 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res18.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Резултати за стабла са 19 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res19.png}
\end{center}
\end{figure}
\end{frame}

\begin{frame}{Резултати за стабла са 20 чворова}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 100mm]{images/res20.png}
\end{center}
\end{figure}
\end{frame}


\begin{frame}{Закључци}
\begin{itemize}
\item \textit{First Zagreb(M1)} има најбољу структурну осетљивост и најмањи максимални отклон
\item \textit{Randic(R)}, \textit{Sum-connectivity(SCI)} и \textit{Geometric-arithmetic($GA_1$)} имају готово исте вредности 
\item \textit{Second Zagreb(М2)} има скоро исту вредност за структурну осетљивост али доста већи максимални отклон у односу на претходна три индекса.
\item Као два најлошија индекса су се показали \textit{Atom-bond connectivity(ABC)} и \textit{Augmented Zagreb(АZI)}
\end{itemize}
\end{frame}



\end{document}
